PsL Monthly 1994 January

home *** CD-ROM | disk | FTP | other *** search

/ PsL Monthly 1994 January / PSL Monthly Shareware CD-ROM (Public Software Library) (January 1994).iso / games / dos / board / backgam.com / BKG.DOC < prev next >

Wrap

Text File | 1987-01-12 | 31.5 KB | 671 lines

Backgammon by Bill Mahoney 7610 Redick Ave Omaha, Nebraska 68122 The game of backgammon has been around for centuries. However, it is still a popular game today, and it is one that I play from time to time. Since I am involved with computer software daily, I thought the game might be an interesting one to implement on a computer. BKG is the result of my efforts. The program may not be the most elegant implementation, and it may not be the best player of the game. But I must be a hacker at heart, because my intention when I started this "pet project" was not so much to construct a great backgammon theorist, but rather to have some fun "teaching" a machine to play. This document is not intended as an instruction booklet on the game. There are so many good backgammon books available at any local bookstore that it would be silly to duplicate their efforts. Thus, I assume that the reader has at least a rudimentary understanding of the game. In order to clarify the description of BKG, however, I have compiled the following notes on the terminology of play: There are two players in the game, and they are usually referred to as white and black. Each player has a number (15) of men on the playing board, as shown below: White's Side 1 2 3 4 5 6 7 8 9 10 11 12 +-----------------------+-------+-----------------------+ | B W | | W B | | B W | | W B | | W | | W B | | W | | B | | W | | B | | | | | | | | | | B | | W | | B | | W | | B | | B W | | W B | | B W | | W B | | B W | +-----------------------+-------+-----------------------+ 24 23 22 21 20 19 18 17 16 15 14 13 Black's Side If you are already familiar with the game, you will note that the board is drawn with respect to black's side. I will use this side for the "human" and BKG will play white. In any case, the object of the game is to move your black players from the low numbered points to the higher numbered points. That is, in a clockwise direction. Meanwhile, white moves his pieces from the higher numbered points to the lower numbered points, in a counter-clockwise direction. Neither player can move "backwards" on the board. The first person to remove all of his men from the board is the winner. A pair of dice is used to de- termine the moves that can be made. Needless to say, things are not quite as easy as they may look. The dice that are used with backgammon relate the possible moves that can be made. Rolling a 3 and a 5, for example, would mean that the player whose turn it is could move one man 3, and another man 5. The "other man" can be the same one, provided that the moves are considered to be two separate moves - one of 3, and one of five. If it makes any difference, the dice can be read as a 5 and a 3, as well. When a player rolls doubles, he or she makes four moves of that number. Double 3's, as an example, allow a player to move four 3's anywhere on the board. Each player must move as many moves as can be made! In some cases, this is not desirable, but it is a rule (enforced by the software, also). If the object of the game is to remove your men from the board, how is this done? The first difficulty is that you must move all of your men to your own inner table prior to taking them off of the playing table. Black has an inner table from point 19 up to point 24. So, prior to black removing men from the table, all of the black players on the board must be between number 19 and number 24. Likewise, white has an inner table from 1 to 6, and all of the white players must be in white's inner table before they can be removed. Another complicating matter is that men may be hit, placing them on the bar. The bar is a sort of "limbo" for players that have been hit. It is the area between the two halves of the playing table. Whenever white leaves one man on a number, that man can be hit by black. Likewise, if the black player lets only one man remain on a number, he is vulnerable to being hit by white. In order to hit a player, all that the opponent must do is place one of his men on the same spot, and move the opponents player to the bar. For example: White's Side 1 2 3 4 5 6 7 8 9 10 11 12 +-----------------------+-------+-----------------------+ | B W | | W B | | B W | | W B | | W | | W B | | W | | | | W | | | | | | | | | | | | B | | W | | B | | W | | B | | B W | | B | | B W | | W B | | W B B B W | +-----------------------+-------+-----------------------+ 24 23 22 21 20 19 18 17 16 15 14 13 Black's Side Suppose that white moves from point number 18 to point number 16: White's Side 1 2 3 4 5 6 7 8 9 10 11 12 +-----------------------+-------+-----------------------+ | B W | | W B | | B W | B | W B | | W | | W B | | W | | | | W | | | | | | | | | | | | B | | W | | B | | W | | B | | B W | | B | | B W | | W B | | B W B W | +-----------------------+-------+-----------------------+ 24 23 22 21 20 19 18 17 16 15 14 13 Black's Side Note that white is moving counter-clockwise, so this is a legal move to make. Once the black player on point number 16 is hit, he is placed on the bar as shown. White has two points with only one man on them, point number 17 and point number 21. The black player could conceivably hit either of these white men on a future move. Except... Once a man is placed on the bar, like the black man in the above example, the player playing black must remove that player from the board before making any other move. The bar is like a point numbered 0 for black, or like a point numbered 25 for white. (In fact, the BKG program uses these numbers.) Thus, it is necessary to move the black player on the bar to one of the points numbered 1 to 6, before any other move can be made. These examples have referred to points with only one player on them. What about points with other numbers? If there are no players at all on a point, then anyone can move to that point with a proper roll of the dice. If there is one of your opponents men on a point, you can bump him onto the bar, as in the above example. Unfortunately, if your opponent has more than one player on a point, you are not allowed to move to that point. Consider this example: White's Side 1 2 3 4 5 6 7 8 9 10 11 12 +-----------------------+-------+-----------------------+ | W W W | | B W W B | | W | | B W B | | W | | W | | | | W | | | | | | | | | | | | | | B | | | | B | | | | B | | B W | | B | | B B W | | W B | | W B B B W | +-----------------------+-------+-----------------------+ 24 23 22 21 20 19 18 17 16 15 14 13 Black's Side In this case, black could move to 21, 18, or 10, bumping one of these players to the bar. Black could also move to any unoccupied number, or to any number occupied by more black players. However, black can not move to points 8 or 13, since these have greater than one white player present on them already. Likewise, white can not occupy points 7, 12, 16, 17, or 19. However, he could bump the player at point 14 onto the bar. At that time, black would have to move the man from the bar onto one of points 1 to 6, prior to making another move. Eventually, black and/or white will have moved all of his players onto the inner table, and they can then be taken off the board. White's Side 1 2 3 4 5 6 7 8 9 10 11 12 +-----------------------+-------+-----------------------+ | W W W W | | W | | W W W W | | | | W W W | | | | W W | | | | W | | | | | | | | | | | | | | | | B b | | | | B B B B | | | | B b B B B | | | | B B B B B | | | +-----------------------+-------+-----------------------+ 24 23 22 21 20 19 18 17 16 15 14 13 Black's Side Suppose black rolls a 2 and a 5 on the dice; the players above which are in lower case can be removed. Other options would include moving a man from point 19 to point 24 (5 points), moving one player from 22 to 24, etc. In this situation, many moves are possible, but it is usually desirable to take players off the board if you can. In the above configuration, white must first move his man from the 8 point into his inner table. Only then can white players be taken off of the board. Chances are, a roll like 2, 3 would be used to move the player at 8 to 6, and the player at 3 off the table. This, in a nutshell, is the essence of basic backgammon. Needless to say, there is a complicating factor, and it is called the doubling cube. The doubling cube normally sits right in the middle of the bar, and has a number 1 on it. Scoring in back- gammon is by wins, and the doubling cube indicates the value in wins that this current game represents. If the doubling cube shows a 1, then this game is worth 1 win. When the doubling cube is in the center of the board, either player may double. However, if the cube is on the other side of the board from a player, then that player may not double. Control of the cube goes back and forth from that point on. As an example, suppose white doubled initially. Then black would be the only player able to double later in the game. If he does, then white can double again, and so on. To double the value of a game, the player states that he/she wishes to double. This must be done before rolling the dice for that turn. The opponent has the option of accepting, whereupon the game proceeds at twice the stakes, or declining. If the player chooses the latter, then the doubling player is the immediate winner of the game. Playing with BKG Operation of the BKG program is relatively simple. After executing BKG from a command prompt, the program asks you to press return; this seeds the random number generator. At that point you have the option of playing white or black. In the cases represented here, I assume that the human plays black, and the computer plays white. The screen, on either the Kaypro or the PC, should draw a playing table similar to the ones outlined in this text. If you have a color monitor on your PC, then the board is in color; otherwise a monochrome monitor works just as well. There are two "dice" drawn in the upper-right corner of the screen. These represent the dice for the game. Also note that there is a doubling cube represented by a box in the center of the screen. Since no player has doubled at the beginning of a game, it is in the center and shows a '1'. When the game starts, one die is rolled by each opponent, and the player with the higher roll starts with that roll. (Variations, including automatic doubling when doubles are rolled, are not a part of the standard rules, and are not included.) Suppose black wins this initial roll, and that the dice show six and one: 1 2 3 4 5 6 7 8 9 10 11 12 +-----------------------+-------+-----------------------+ | B W | | W B | | B W | | W B | | W | | W B | | W | | B | | W | +---+ | B | | | | 1 | | | | | +---+ | | | B | | W | | B | | W | | B | | B W | | W B | | B W | | W B | | B W | +-----------------------+-------+-----------------------+ 24 23 22 21 20 19 18 17 16 15 14 13 Black rolls a 6, 1 and gets to start. Your move: This is a good roll to get for black, because he can make his 18 point by moving someone from the 12 point 6 places, and someone from the 17 point 1 point. To do this, enter the following at the prompt: Your move: 12/6 17/1 The slash is used to separate the source point from the distance desired. Entering "17/1 12/6" would have the same result - the order is not important in this case. Just for your reference, here are some of the other possible moves, and the representation for each: Your move: 1/1 1/6 Your move: 17/6 17/1 Your move: 12/6 1/1 Your move: 19/1 1/6 Your move: 12/6 18/1 (but not 12/1 13/6) Your move: 12/6/1 (but not 12/1/6) The last two examples accomplish the same result; the second is a shorthand for the first. In any case, the playing board should look like this: 1 2 3 4 5 6 7 8 9 10 11 12 +-----------------------+-------+-----------------------+ | B W | | W B | | B W | | W B | | W | | W B | | W | | B | | W | +---+ | | | | | 1 | | | | | +---+ | | | B | | W | | B | | W | | B | | W | | W B | | B B W | | W B | | B B W | +-----------------------+-------+-----------------------+ 24 23 22 21 20 19 18 17 16 15 14 13 Black rolls a 6, 1 and gets to start. Your move: 12/6 17/1 Now, white (the BKG program) will roll the dice. Suppose it rolls a one and three. It might make the following move: 1 2 3 4 5 6 7 8 9 10 11 12 +-----------------------+-------+-----------------------+ | B W W | | W B | | B W W | | W B | | W | | B | | W | | B | | | +---+ | B | | | | 1 | | | | | +---+ | | | B | | W | | B | | W | | B | | B W | | W B | | B W | | W B | | B W | +-----------------------+-------+-----------------------+ 24 23 22 21 20 19 18 17 16 15 14 13 White rolls a 1, 3 and moves 8/3 6/1 Return to roll: White, since it is the computer, makes its moves automatically, of course. Note that the dice are not rolled for you once the opponent has completed his move. This is because you may wish to double at this point. You could just roll the dice by hitting return, or you can type "double" (or just "d"). This is similar to asking the person across the table if he will take a double at that point. The BKG program will either accept, by saying "yes" or decline, and lose the game. The "return to roll" prompt also allows you to quit the game by typing "quit". Suppose you press return, and roll a double-five. Some of your options at this point are: Your move: 12/5 12/5 12/5 12/5 Your move: 12/5 12/5 17/5 17/5 Your move: 12/5/5 12/5/5 (same as previous example) Note that the black players at point one and point 19 can not move, since there are more than two white players exactly five points away. Let's move "12/5/5 12/5/5", resulting in: 1 2 3 4 5 6 7 8 9 10 11 12 +-----------------------+-------+-----------------------+ | B W W | | W B | | B W W | | W B | | W | | B | | W | | | | | | | | | +---+ | | | | | 1 | | | | B | +---+ | W | | B | | W | | B | | B W | | W B B | | B W | | W B B | | B W | +-----------------------+-------+-----------------------+ 24 23 22 21 20 19 18 17 16 15 14 13 White rolls a ... Return to roll: Play alternates back and forth in this manner, until a complication occurs: 1 2 3 4 5 6 7 8 9 10 11 12 +-----------------------+-------+-----------------------+ | W W | | B W W B B | | W W | | W W B | | W | | W | | W | | | | | | | | | +---+ | | | | | 1 | | | | | +---+ | | | B | | | | B | | B W | | B B | | B W | | B B B | | B B W W | +-----------------------+-------+-----------------------+ 24 23 22 21 20 19 18 17 16 15 14 13 White doubles. Do you accept? You have the option at this time of either typing 'Y', and proceeding on twice the stakes, or declining by typing 'N' and losing this game. Suppose we accept; then the cube is given to our side, and the computer player is not able to double until after we do. We have "control" of the cube: 1 2 3 4 5 6 7 8 9 10 11 12 +-----------------------+-------+-----------------------+ | W W | | B W W B B | | W W | | W W B | | W | | W | | W | | | | | | | | | | | | | | | | | | | | B | | | | B | +---+ | B W | | B B | | 1 | | B W | | B B B | +---+ | B B W W | +-----------------------+-------+-----------------------+ 24 23 22 21 20 19 18 17 16 15 14 13 White rolls double threes, White has rolled a lucky double, and he moves "13/3/3 6/3 6/3". This has the unfortunate aspect of knocking two black players onto the bar: 1 2 3 4 5 6 7 8 9 10 11 12 +-----------------------+-------+-----------------------+ | W W W | | W W W B | | W W W | B B | W W B | | | | W | | | | | | | | | | | | | | | | | | | | | | B | | | | B | +---+ | B W | | B B | | 1 | | B W | | B B B | +---+ | B B W W | +-----------------------+-------+-----------------------+ 24 23 22 21 20 19 18 17 16 15 14 13 White rolls double threes, and moves 13/3 10/3 6/3 6/3 Return to roll: Suppose we press return, and roll a three and a four. The rules of play specifically forbid a player from moving on the board until all of that players men are off of the bar. In the case of this roll, we can not put both men onto the table, because point number three is occupied. Thus, we can only make one move: 1 2 3 4 5 6 7 8 9 10 11 12 +-----------------------+-------+-----------------------+ | W B W W | | W W W B | | W W W | B | W W B | | | | W | | | | | | | | | | | | | | | | | | | | | | B | | | | B | +---+ | B W | | B B | | 1 | | B W | | B B B | +---+ | B B W W | +-----------------------+-------+-----------------------+ 24 23 22 21 20 19 18 17 16 15 14 13 White rolls double threes, and moves 13/3 10/3 6/3 6/3 Your move: b/4 When moving off of the bar/ specify "b" as the source, and specify the distance as you normally would. Suppose we had rolled a three and six. Then we would have nothing we could play, and it is immediately white's turn again. This is checked automatically. Also, we can not move "b/3 18/4", because of the above rules. Play continues in this way until near the end of the game. Suppose we are just about finished: 1 2 3 4 5 6 7 8 9 10 11 12 +-----------------------+-------+-----------------------+ | W W W W W W | | | | W W W W W | | | | W W W | | | | W | | | | | | | | | | | | | | | | | | | | B B | | | | B B | +---+ | | | B B B B | | 1 | | | | B B B B B | +---+ | B B | +-----------------------+-------+-----------------------+ 24 23 22 21 20 19 18 17 16 15 14 13 White rolls double threes, and moves 13/3 10/3 6/3 6/3 Return to roll: At this point we have little we can do except for taking the men off of points 17 and 18 and into the inner table. Remember, you must have all players in this area before removing them from the board. Removing players is exactly the same as moving them around the board. Once the players on 17 and 18 are taken to the left, suppose we roll double fours. We could then move something like "21/4 19/4 19/4 19/4". The man on point 21 is gone - he has been removed from the table. The first one to remove all men is the winner. Note that in backgammon, if you have removed all of your men prior to the opponent getting all of his men to his inner table, then you win twice the value of the game. This is called a gammon. When you win a gammon and the game has doubled back and forth, you win twice the number shown on the cube. The ultimate disgrace is to backgammon your opponent. This happens when you have removed all of your players from the table, but the opponent has players left in your inner table. This is rather rare, but is worth three times the value of the game should it happen. About the Software The system consists of the following files: BKG.C - This is the main routine for the back- gammon player. EVAL.C - These routines are the heuristics used to make semi-intelligent moves. When to double and not double is also included in here. IBMUTILS.C - These are utility functions for running on the IBM PC or clone. Link these in when running on a PC, and leave out Kayutils. KAYUTILS.C - This file contains the utilities for drawing on the Kaypro screen. You link in these utilities when running on a Kaypro with CP/M. MOVE.C - This handles removing a player from the board, and putting him in a different place. MOVEGEN.C - This is the move generator. It takes a board configuration, and what the dice show, and generates all possible moves given that board and roll. BKG.H - This file contains all of the (unfortunate) globals and #define's for the rest of the software. This file is included everywhere else. BKG.TXT - You're reading it. BKG.PRN - In case you don't have NewWord or Word- star. These are designed to be compiled and run on a Kaypro with graph- ics, using the BDS C compiler, or on an IBM PC clone using the Computer Innovations C86 compiler. There are two computer- dependent libraries that need to be compiled and linked with the rest of the source. "Kayutils.c" is the utility file fur running on the Kaypro computers. "Ibmutils.c" contains the same routines, but is PC dependent for the PC clones. (You wouldn't buy the real thing, now, would you?) Compile each of the C source files. Then link them. Under BDS C I use the L2 linker instead of CLINK, but each works equally well: A0>L2 bkg movegen move screen eval -l kayutils or A0>clink bkg movegen move screen eval kayutils To link code compiled with the C86 compiler, note that the small model can/should be used to compile all of the source files. Then: A>link bkg+movegen+move+screen+eval+ibmutils,,,ibmpcs+c86s2s using the IBM linker. Lastly, The rules used to implement this game are found in "The Back- gammon Book" by Oswald Jacoby and John Crawford. This was also the source for some of the heuristics concerning the doubling cube. I found this book at my local B. Daltons, of course. he source for some of the h